// 笔试强训day28:二叉树中的最大路径和

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    pair<int, int> maxLenthSum(TreeNode* root, int& maxnode)//first单边最大，second当前最大
    {
        if(root == nullptr)
            return {0, 0};
        if(root->val > maxnode)
            maxnode = root->val;
        pair<int, int> leftsum = maxLenthSum(root->left, maxnode);
        pair<int, int> rightsum = maxLenthSum(root->right, maxnode);
        int first = root->val + max(leftsum.first, rightsum.first);
        int second = leftsum.first + rightsum.first + root->val;
        second = max(second, max(leftsum.second, rightsum.second));
        return {max(0, first), max(0, second)};
    }
    
    int maxPathSum(TreeNode* root) {
        // write code here
        int maxnode = root->val;
        pair<int, int> maxsum = maxLenthSum(root, maxnode);
        return maxsum.second == 0 ? maxnode : maxsum.second;
    }
};